package util;

import java.util.LinkedList;

public class Search {
	public static Object[] search(String str, String[] dict) {
		str= str.trim();
		if(str.length()==0) return dict;

		LinkedList<String> results[] = new LinkedList[15];
		for(int i=0; i<results.length; i++) results[i]= new LinkedList<String>();
		for(String key : dict) {
			int score1 = 0, score2 = 0;//lavenshteinDistance(str,key,true);
			String[] tokens1 = str.split(" ");
			String[] tokens2 = key.split(" ");
			for(String s1 : tokens1) {
				int min = Integer.MAX_VALUE;
				for(String s2 : tokens2) {
					int val = lavenshteinDistance(s1,s2,false);
					if(val<min) min=val;
				}
				score1+=min;
			}
			for(String s1 : tokens2) {
				int min = Integer.MAX_VALUE;
				for(String s2 : tokens1) {
					int val = lavenshteinDistance(s1,s2,false);
					if(val<min) min=val;
				}
				score2+=min;
			}
			int score = Math.min(score1, score2);
			if(score<results.length) {
				results[score].add(key);
			}
		}
		LinkedList<String> ret = new LinkedList(results[0]);
		for(int i=1; i<results.length; i++) ret.addAll(results[i]);
		return ret.toArray();
	}
	public static int lavenshteinDistance(String word1, String word2, boolean partialMatch) {
		word1=word1.trim().toLowerCase();
		word2=word2.trim().toLowerCase();
		char [] a, b;
		if(word1.length()>word2.length()) {
			a=word1.toCharArray();
			b=word2.toCharArray();
		} else {
			a=word2.toCharArray();
			b=word1.toCharArray();
		}
		int [] arr = new int[a.length+1];

		for(int i=0; i<=a.length; i++)
			arr[i]=i;
		int prev;
		for(int j=1; j<=b.length; j++) {
			prev=arr[0];
			arr[0]=j;
			for(int i=1; i<=a.length; i++) {
				int v=Math.min(prev, Math.min(arr[i-1], arr[i]));
				prev=arr[i];
				arr[i]=v;
				if(a[i-1]!=b[j-1]) arr[i]++;
			}
		}
		/*
		if(partialMatch) {
			int min = arr[b.length];
			for(int i=b.length; i<a.length; i++)
				if(min>arr[i]) min=arr[i];
			return min;
		} */
		return arr[a.length];
	}
	public static void print(int[] arr) {
		System.out.println(java.util.Arrays.toString(arr));
	}
}
